1. Field of the Invention
The invention has generally to do with finding values of parameters of a system which satisfy a set of constraints and specifically to do with techniques for finding such values which do not "get stuck" at local minima.
2. Description of the Prior Art
Many problems in artificial intelligence, computer science, manufacturing, business, and other fields can be posed as constraint satisfaction problems. A constraint satisfaction problem consists of a set of variables, a set of possible values for each variables, and a set of constraints between subsets of the variables. Each constraint on a subset of the variables restricts the possible values that may be simultaneously assigned to those variables. A solution to a constraint satisfaction problem is an assignment of values to each variable such that all constraints are satisfied.
An important class of constraint satisfaction problems are conjunctive normal form Boolean constraint satisfaction problems. (This class is commonly named "CNF".) In such problems, each variable has to be assigned one of just two possible values: true or false. A literal is defined as either a variable or the negation of a variable. Each constraint is then given by a clause in propositional logic, which is a disjunction of literals.
For example, let the variables be A, B, and C. Let there be three constraints, where the first is "A or C"; the second is "(not A) or C"; and the third is "B or (not C)". The first constraints specifies that either A is set to true, or B is set to true; or both are set to true. (Henceforth, "or" will always be meant in this inclusive sense, unless specified otherwise.) This eliminates the possibility of setting both A and C to false simultaneously. The second constraint specifies that either A is set to false (which is indicated by the "not"), or C is set to true. Finally, the third constraint specifies that either B is set to true or C is set to false.
One of the solutions to this problem is the assignment of false to A, true to B, and true to C. Every constraint is satisfied by this assignment.
The problem of solving CNF problems is one of the central problems in computer science, because many other decision and optimization problems can be translated into this form. Cook (1971) proved that any problem that can be solved by a non-deterministic Turing machine in polynomial time (that is, any problem in the class NP) can be reduced to a CNF problem (S. A. Cook, "The Complexity of Theorem-Proving Procedures", in Proceedings of the 3rd Annual ACM Symposium on the Theory of Computing, pp. 151-158, 1971). A catalogue of such problems from many areas of computer science appears in M. R. Carey and D. S. Johnson, Computers and Intractability, 1979, including integer programming, the travelling salesman problem, graph coloring, and many others.
An efficient way of solving CNF problems would immediately yield an efficient way of solving all the different kinds of problems in NP. It is believed that no efficient procedure exists for solving all instances of CNF problems. However, it is possible and useful to devise procedures that efficiently solve many, if not all, instances of CNF problems. The invention pertains to such a method.
One way of solving constraint satisfaction problems is by performing a systematic search of all possible assignments of values to variables. This is the basis of the Davis-Putnam algorithm (M. Davis and H. Putnam, "A computing procedure for quantification theory", Journal of the Association for Computing Machinery, vol. 7, 1960, pp. 201-215, 1960) which is the most widely-used procedure.
An alternative approach is based on greedy local search, which is also referred to as heuristic repair (see D. S. Johnson, C. H. Papadimmitrou, and M. Yannakakis, "How easy is local search?", Journal of Computer and System Sciences, vol. 37, pp. 79-100, 1988). The idea of this approach is to start with some initial assignment of values to variables, which may be generated randomly or by some other method. The initial assignment will in general violate one or more constraints. The algorithm then tries to reduce the total number of violated constraints by changing the value assigned to one of the variables. Such changes are made until all constraints are satisfied, or the algorithm reaches some pre-set maximum number of changes. If an assignment is not found, one can repeat this procedure, starting at a different initial assignment. This method has been successfully applied to CNF problems, as described in B. Selman, H. Levesque, an D. Mitchell, "A New Method for Solving Hard Satisfiability Problems", in Proceedings of the Tenth National Conference on Artificial Intelligence, pp. 440-446, 1992, and in J. Gu, "Efficient local search for very large-scale satisfiability problems", in Sigart Bulletin, vol. 3, no. 1, pp. 8-12, 1992.
The standard greedy local search algorithm considers all constraints to be of equal importance when deciding which variable to modify. This can cause the procedure to be unable to solve problems where some constraints are very hard to satisfy. The phenomenon in which a greedy local search procedure reaches a state in which it cannot proceed to satisfy the remaining violated constraints is called a local minima. One proposal for escaping from such local minima is the method of simulated annealing (S. Kirkpatrick, C. D. Gelett, and M. P. Vecchi, "Optimization by simulated annealing", Science, vol. 220, pp. 621-630, 1983), which introduces random modifications of the assignment. The invention described here is an alternative strategy for alleviating the problem of local minima, and thus extends the range of applicability of the greedy local search method.